//ArrayList的具体实现

// 自己实现一个简单的顺序表
// 直接以 int 为例就行表示了, 就不写泛型了.
public class MyArrayList {
    // 真正存储数据. 顺序表本身就是基于数组的封装.
    private int[] arr;
    // 约定 arr 中的前 size 个元素, 表示有效元素.
    private int size = 0;

    ///////////////////////////////////////////////////
    // 这个部分是 MyArrayList 的正式代码
    ///////////////////////////////////////////////////
    public MyArrayList() {
        // 无参数版本默认的容量 10
        arr = new int[10];
    }

    public MyArrayList(int capacity) {
        arr = new int[capacity];
    }

    // 获取元素个数
    public int size() {
        return size;
    }

    // 新增元素, 尾插
    public void add(int val) {
        // 把新的元素放到最后一个位置上. 下标为 size 的位置
        // [0, size) 区间
        if (size == arr.length) {
            // 数组满了, 先扩容
            resize();
        }
        arr[size] = val;
        size++;
    }

    private void resize() {
        // 1. 创建一个更长的数组. 容量扩展到 1.5 倍
        int[] newArr = new int[(int) (arr.length * 1.5)];
        // 2. 把原来数组的元素复制到新数组上.
        for (int i = 0; i < size; i++) {
            newArr[i] = arr[i];
        }
        // 3. 用新的数组替代旧数组
        //    此时旧的数组就会被垃圾回收给释放掉.
        arr = newArr;
    }

    // 任意位置新增.
    public void add(int index, int val) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("Index out of bounds");
        }
        // 如果数组已经满了, 继续添加元素, 也是要先扩容
        if (size == arr.length) {
            resize();
        }
        // 搬运元素的操作. 从后往前, 依次把每个元素都往后搬运一个位置.
        // 如果元素本身的下标是 i, 就把这个元素赋值到 i+1 的位置上.
        // index 位置的元素也需要往后搬运一下, i >= index
        for (int i = size - 1; i >= index; i--) {
            arr[i + 1] = arr[i];
        }
        // 此时就相当于把 index 位置已经腾出来了. 把新元素放到 index 位置上就好了.
        arr[index] = val;
        // 不要忘记更新 size
        size++;
    }

    // 根据下标获取元素
    public int get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("下标越界: " + index);
        }
        return arr[index];
    }

    // 根据下标设置元素
    public void set(int index, int val) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("下标越界: " + index);
        }
        arr[index] = val;
    }

    // 删除元素, 按照下标删除
    // 希望 remove 返回被删除的元素.
    public int remove(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("下标越界: " + index);
        }
        int result = arr[index];
        // 这个逻辑就已经涵盖到下面的一般情况了
//        if (index == size - 1) {
//            // 尾删
//            size--;
//            return result;
//        }
        // 边界值, 非常容易出错的!! 一定要带入具体数字来分析.
        for (int i = index; i < size - 1; i++) {
            arr[i] = arr[i + 1];
        }
        // 不要忘记 size-- 的情况
        size--;
        return result;
    }

    // 删除元素, 按照值来删除
    // 查找过程中的比较, 应该使用 equals 来进行.
    // 由于此处是 int, 直接用 == 即可.
    public void delete(int val) {
        // 1. 先找到这个值所在的位置.
//        int index = 0;
//        for (; index < size; index++) {
//            if (arr[index] == val) {
//                // 找到了.
//                break;
//            }
//        }
//        if (index == size) {
//            // 没有找到, 元素不存在
//            // 不必进行删除了.
//            return;
//        }
        int index = indexOf(val);
        if (index == -1) {
            return;
        }

        // 2. 然后通过上述 remove 的过程来进行搬运式的删除.
        //    index 就是要删除的元素位置
//        for (int i = index; i < size - 1; i++) {
//            arr[i] = arr[i + 1];
//        }
//        size--;
        remove(index);
    }

    // 判定元素是否存在
    public boolean contains(int val) {
        for (int i = 0; i < size; i++) {
            if (arr[i] == val) {
                return true;
            }
        }
        return false;
    }

    // 查找元素所在的位置
    public int indexOf(int val) {
        for (int i = 0; i < size; i++) {
            if (arr[i] == val) {
                return i;
            }
        }
        return -1;
    }

    public int lastIndexOf(int val) {
        for (int i = size - 1; i >= 0; i--) {
            if (arr[i] == val) {
                return i;
            }
        }
        return -1;
    }

    public void clear() {
        // 删除所有元素.
        // 逻辑删除即可.
        // 把每个元素都设为 0, 不需要的.
//        for (int i = 0; i < size; i++) {
//            arr[i] = 0;
//        }
        size = 0;

        // 其实不能这么搞.
        // clear 清空元素. 清空之后, 这个顺序表还是要接着用的.
        // arr = null;
        // 是否进行缩容? 一般也是不需要的. 当前编程过程中, 内存空间不足问题, 不是主要矛盾.
        // arr = new int[10];
    }

    // 打印操作. 搞一个 toString, 把 MyArrayList 转化为字符串.
    @Override
    public String toString() {
        // 打印的格式形如: [1, 2, 3, 4]
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append("[");
        for (int i = 0; i < size; i++) {
            stringBuilder.append(arr[i]);
            if (i < size - 1) {
                // i == size -1 时, 就是最后一个元素, 最后一个元素不添加 ,
                stringBuilder.append(", ");
            }
        }
        stringBuilder.append("]");
        return stringBuilder.toString();
    }

    //////////////////////////////////////////////////////////////////
    // 下列是一些测试方法
    //////////////////////////////////////////////////////////////////

    private static void test1() {
        MyArrayList list = new MyArrayList();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        System.out.println(list.size());
        System.out.println(list);
    }

    private static void test2() {
        MyArrayList list = new MyArrayList(10);
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(0, 100);
        list.add(1, 200);
        list.add(2, 300);
        System.out.println(list);
    }

    private static void test3() {
        MyArrayList list = new MyArrayList(10);
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);
        list.add(6);
        list.add(7);

        list.remove(0);
        System.out.println(list);
        list.remove(2);
        System.out.println(list);
        list.remove(4);
        System.out.println(list);
        list.remove(100);
        System.out.println(list);
    }

    private static void test4() {
        MyArrayList list = new MyArrayList(10);
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);
        list.add(6);
        list.add(7);

        list.delete(3);
        System.out.println(list);
        list.delete(5);
        System.out.println(list);
        list.delete(100);
        System.out.println(list);
    }

    private static void test5() {
        MyArrayList list = new MyArrayList(10);
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);
        list.add(6);
        list.add(7);

        if (list.contains(3)) {
            System.out.println("OK");
        } else {
            System.out.println("failed");
        }

        if (!list.contains(100)) {
            System.out.println("OK");
        } else {
            System.out.println("failed");
        }

        if (list.indexOf(5) == 4) {
            System.out.println("OK");
        } else {
            System.out.println("failed");
        }

        if (list.indexOf(100) == -1) {
            System.out.println("OK");
        } else {
            System.out.println("failed");
        }

        if (list.lastIndexOf(5) == 4) {
            System.out.println("OK");
        } else {
            System.out.println("failed");
        }

        if (list.lastIndexOf(100) == -1) {
            System.out.println("OK");
        } else {
            System.out.println("failed");
        }

//        System.out.println(list.contains(3));
//        System.out.println(list.contains(100));
//        System.out.println(list.indexOf(5));
//        System.out.println(list.indexOf(100));
    }

    public static void main(String[] args) {
        // test1();
        // test2();
        // test3();
        // test4();
        test5();
    }
}
